package leetcode_800;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 *@author 周杨
 *RangeModule_715 不断插入移除区间 区间可以重叠 实现区间数字的查询
 *describe:用map 也可以用线段树 AC 30%
 *2018年10月11日 下午6:01:10
 */
public class RangeModule_715 {
	TreeMap<Integer, Integer> map;

	public RangeModule_715() {
		map = new TreeMap<>();
	}

	public void addRange(int left, int right) {
		if (right <= left)
			return;
		Integer start = map.floorKey(left);
		Integer end = map.floorKey(right);
		if (start == null && end == null) {
			map.put(left, right);
		} else if (start != null && map.get(start) >= left) {
			map.put(start, Math.max(map.get(end), Math.max(map.get(start), right)));
		} else {
			map.put(left, Math.max(map.get(end), right));
		}
		// clean up intermediate intervals
		Map<Integer, Integer> subMap = map.subMap(left, false, right, true);
		Set<Integer> set = new HashSet<Integer>(subMap.keySet());
		map.keySet().removeAll(set);
	}

	public boolean queryRange(int left, int right) {
		Integer start = map.floorKey(left);
		if (start == null)
			return false;
		return map.get(start) >= right;
	}

	public void removeRange(int left, int right) {
		if (right <= left)
			return;
		Integer start = map.floorKey(left);
		Integer end = map.floorKey(right);
		if (end != null && map.get(end) > right) {
			map.put(right, map.get(end));
		}
		if (start != null && map.get(start) > left) {
			map.put(start, left);
		}
		// clean up intermediate intervals
		Map<Integer, Integer> subMap = map.subMap(left, true, right, false);
		Set<Integer> set = new HashSet<Integer>(subMap.keySet());
		map.keySet().removeAll(set);

	}
}
